package pers.sloera.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * 循环码排列
 *
 * @author sloera
 * @date 2023-02-23 22:48:08
 */
class CircularPermutationInBinaryRepresentation {
    public static void main(String[] args) {
        Solution solution = new CircularPermutationInBinaryRepresentation().new Solution();
        System.out.println(solution.circularPermutation(2, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> circularPermutation(int n, int start) {
            // 生成gray code，然后从start位置重新开始排列
            // gray code，每次变化时，只有一位变动，相比于正常的二进制，所需的模拟电路变化更少，如0111到1000
            // 公式证明见：https://leetcode.cn/problems/gray-code/solution/ge-lei-bian-ma-by-leetcode-solution-cqi7/
            int index = 0;
            ArrayList<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < 1 << n; i++) {
                // g_i = i ^ [i/2]
                int grayCode = i ^ (i >> 1);
                tmp.add(grayCode);
                if (grayCode == start) {
                    index = i;
                }
            }
            List<Integer> result = new ArrayList<>();
            result.addAll(tmp.subList(index, tmp.size()));
            result.addAll(tmp.subList(0, index));
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
